<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>29. 两数相除</title>
</head>
<body>
  <script>
//     给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

// 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

// 返回被除数 dividend 除以除数 divisor 得到的 商 。

// 注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231,  231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

 

// 示例 1:

// 输入: dividend = 10, divisor = 3
// 输出: 3
// 解释: 10/3 = 3.33333.. ，向零截断后得到 3 。
// 示例 2:

// 输入: dividend = 7, divisor = -3
// 输出: -2
// 解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。
 

// 提示：

// -231 <= dividend, divisor <= 231 - 1
// divisor != 0

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
 var divide = function(a, b) {
    // 特殊情况
    if (!a) return 0;
    const [MIN, MAX] = [-(2 ** 31), 2 ** 31 - 1];
    if (a === MIN && b === -1) return MAX;
    if (a === MIN && b === 1) return MIN;

    // 是否为负数
    const isNeg = (a ^ b) < 0;
    // 取绝对值
    [a, b] = [Math.abs(a), Math.abs(b)];

    let res = 0;
    for (let i = 31; i >= 0; i--) {
        // 找出满足条件的最大的倍数
        if (a >>> i >= b) {
            // 累加上这个倍数
            res += 1 << i;
            // 被除数减去这个倍数*b
            a -= b << i;
        }
    }

    return isNeg ? -res : res;
    
  };
  </script>
</body>
</html>